package 动态规划专项训练.动态规划训练2;

/**买卖股票的最佳时机 III
 * @author zx
 * @create 2022-04-08 11:31
 */
public class Num123 {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if(n == 0){
            return 0;
        }
        int[][] f = new int[n + 1][5 + 1];
        //初始条件
        //刚开始(前0天),处于阶段1,最大利润为0
        f[0][1] = 0;
        f[0][2] = f[0][3] = f[0][4] = f[0][5] = Integer.MIN_VALUE;
        for(int i = 1;i <= n;i++){
            //1,3,5
            for(int j = 1;j <= 5;j += 2){
                //max{f[i - 1][j],f[i - 1][j - 1] + Pi - 1 - Pi - 2}
                f[i][j] = f[i - 1][j];
                if(j > 1 && i > 1 && f[i - 1][j - 1] != Integer.MIN_VALUE){
                    f[i][j] = Math.max(f[i][j],f[i - 1][j - 1] + prices[i - 1] - prices[i - 2]);
                }
            }
            for(int j = 2;j <= 5;j += 2){
                //max{f[i - 1][j] + Pi - 1 - Pi - 2,f[i - 1][j - 1],f[i - 1][j - 2] + Pi-1 - Pi-2}
                f[i][j] = f[i - 1][j - 1];
                if(i > 1 && f[i - 1][j] != Integer.MIN_VALUE){
                    f[i][j] = Math.max(f[i][j],f[i - 1][j] + prices[i - 1] - prices[i - 2]);
                }
                if(j > 2 && i > 1 && f[i - 1][j - 2] != Integer.MIN_VALUE){
                    f[i][j] = Math.max(f[i][j],f[i - 1][j - 2] + prices[i - 1] - prices[i - 2]);
                }
            }
        }
        return Math.max(Math.max(f[n][1],f[n][3]),f[n][5]);
    }
}
